import { IDIterator } from "../types";
import BaseLinkList from "./base";
/**
 * 链表节点
 */
export class DNode<T> {
    public value: T | undefined;
    public next: DNode<T> | null
    public prev: DNode<T> | null
    constructor(value: T | undefined, prev: DNode<T> | null, next: DNode<T> | null) {
        this.value = value
        this.next = next
        this.prev = prev
    }
}
/**
 * 双向循环链表
 */
export default class DoubleCycleLinkedList<T> extends BaseLinkList<T> {
    private sizes: number = 0
    private root: DNode<T> | null = null

    /**
     * 获取根元素
     */
    getRoot() {
        return this.root;
    }

    /**
     * 获取链表中元素的数量
     */
    size() {
        return this.sizes;
    }

    /**
     * 链表是否为空
     */
    isEmpty() {
        return this.sizes === 0
    }

    /**
     * 链表是否包含元素T
     * @param element 
     */
    contains(element: T) {
        return this.indexOf(element) !== -1
    }

    /**
     * 添加元素到尾部
     * @param element 
     */
    add(element: T) {
        // 检验element
        this.checkElement(element);
        // 往尾部添加元素
        this.addToIndex(this.sizes, element)
    }

    /**
     * 往索引index处添加元素
     * @param index 
     * @param element 
     */
    addToIndex(index: number, element: T) {
        const sizes = this.sizes;
        if (index < 0 || index > sizes) { throw new Error('索引越界~~') }
        // 首次添加
        if (sizes === 0) {
            this.root = new DNode(element, null, null);
            this.root.prev = this.root;
            this.root.next = this.root;
            this.sizes++;
            return;
        }

        const root = this.root;
        // 至少有一个元素
        if (index === 0) {
            // 往头加入新节点

            // 创建新节点
            const newNode = new DNode(element, root!.prev, root)
            // 改变原来的prev
            root!.prev!.next = newNode;
            root!.prev = newNode;

            // 更改root的指向
            this.root = newNode;
        } else if (index === sizes) {
            // 往尾部添加元素
            // 获取最后一个元素
            const lastEle = this.root?.prev!;


            // 添加到最后
            lastEle!.next = new DNode(element, lastEle, this.root);

            // 修改根元素的prev为 最后的元素
            this.root!.prev = lastEle.next
        } else {
            // 往其他位置添加元素
            this.iterator((node, i) => {
                // 找到索引位置的索引
                if (index === i) {
                    const newNode = new DNode(element, node.prev, node)
                    node.prev!.next = newNode;
                    node.prev = newNode;
                    return true
                }
                return false
            })
        }
        // 长度加一
        this.sizes++;
    }

    /**
     * 往队头添加元素
     * @param element 
     */
    unshift(element: T) {
        // debugger
        if (this.isEmpty()) return 0;
        // 往索引0处添加
        this.addToIndex(0, element)
        return this.sizes;
    }

    /**
     * 删除对头元素并删除
     */
    shift() {
        if (this.isEmpty()) return null;
        return this.remove(0);
    }

    /**
     * 删除队尾元素并取出
     */
    pop() {
        // 空的
        if (this.isEmpty()) return null;
        return this.remove(this.sizes - 1)
    }

    /**
     * 获取index处的元素
     * @param index 
     */
    get(index: number) {
        // 链表为空
        if (this.isEmpty()) return;
        this.checkIndex(index);
        let val: DNode<T> | null = null
        this.iterator((node, i) => {
            if (index === i) {
                val = node;
                return true;
            }
            return false
        })

        return val!
    }

    /**
     * 修改index处的元素为element
     * @param index 
     * @param element 
     */
    set(index: number, element: T) {
        // 检验参数
        this.checkIndex(index);
        this.checkElement(element);

        this.iterator((node, i) => {
            if (i === index) {
                node.value = element
                return true
            }
            return false
        })

        return element
    }

    /**
     * 获取元素T的索引
     */
    indexOf(element: T) {
        this.checkElement(element);
        let i = -1;
        this.iterator((node, index) => {
            // 元素相等
            if (node.value === element) {
                i = index
                return true;
            }
            return false
        })
        return i
    }

    /**
     * 根据index获取节点
     * @param index 
     */
    private node(index: number): DNode<T> {
        let n!: DNode<T>;
        this.iterator((node, i) => {
            if (i === index) {
                n = node;
                return true
            }
            return false;
        })
        return n
    }

    /**
     * 从链表中删除element
     * @param element 
     */
    remove(index: number): T {
        // 校验element
        this.checkIndex(index)
        const element = this.node(index);

        if (index === 0) {
            if (this.sizes === 1) {
                // 只有一个节点， 清除根即可
                this.root = null
            } else {
                // 删除根节点
                element.next!.prev = element?.prev!;
                // 更改最后的next
                element.prev!.next = element.next

                // 更改root
                this.root = element.next;
            }
        } else  {
            //  删除的不是根元素 
            // 改变next
            element.prev!.next = element.next
            // 改变prev
            element.next!.prev = element.prev;
        } 

        this.sizes--;
        return element.value!;
    }

    /**
     * 清空链表
     */
    clear() {
        // 清空
        this.sizes = 0;
        this.root = null;
    }

    /**
     * 获取最后一个元素
     */
    getLastEle() {
        if (this.isEmpty()) return null;
        return this.root!.prev!.value
    }

    /**
     * 链表迭代器
     */
    forEach(cb: IDIterator<T>) {
        if (this.isEmpty()) return;
        this.iterator((node, i) => {
            cb(node, i)
            return false
        })
    }


    /**
     * 遍历链表
     * @param cb 
     */
    private iterator(cb: (node: DNode<T>, index: number) => boolean) {
        let i = 0,
            sizes = this.sizes,
            root = this.root;

        for (; i < sizes; i++) {
            // root没有next 或者 cb停止遍历了
            if (root === null || cb(root!, i)) break;
            root = root!.next;
        }
    }

    /**
     * 检验元素的合法性
     * @param element 
     */
    private checkElement(element: T) {
        if (element == null) {
            throw new Error('元素不能为空~~')
        }
    }

    /**
     * 校验索引
     * @param index 
     */
    private checkIndex(index: number) {
        if (index < 0 || index >= this.sizes) {
            throw new Error('索引越界~~')
        }
    }
}